#include <stdio.h>
#include <stdlib.h>
#include <math.h>

/*
	实现 Dijkstra (迪杰斯特拉) 算法。
*/

void Dijkstra(int start, float (*graph)[7])
{
	int n = sizeof(*graph) / sizeof(float);
	int path[n];
	float distances[n];
	int i;
	for (i = 0; i < n; i++)
	{
		path[i] = -1;
		distances[i] = INFINITY;
	}
	distances[start] = 0;
	float distance;
	int dijkstra(float(*graph)[7], int vertex)
	{
		int j;
		for (j = 0; j < n; j++)
		{
			distance = distances[vertex] + graph[vertex][j];
			if (distance < distances[j])
			{
				distances[j] = distance;
				path[j] = vertex;
				dijkstra(graph, j);
			}
		}
		return 0;
	}
	dijkstra(graph, start);
	for (i = 0; i < n; i++)
	{
		printf("point=%d,distance=%f,path=%d\n", i, distances[i], path[i]);
	}
}

int main()
{
	float graph[7][7] = {
		{0, 2, INFINITY, 1, INFINITY, INFINITY, INFINITY},
		{INFINITY, 0, INFINITY, INFINITY, 10, INFINITY, INFINITY},
		{4, INFINITY, 0, INFINITY, INFINITY, 5, INFINITY},
		{INFINITY, INFINITY, 2, 0, 2, 8, 4},
		{INFINITY, INFINITY, INFINITY, INFINITY, 0, INFINITY, 6},
		{INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, 0, INFINITY},
		{INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, 1, 0}};
	Dijkstra(0, graph);
	return 0;
}
